package xyz.sekai52799.answer.a3001_a3200;

import java.util.ArrayList;
import java.util.List;

public class Question3101 {
//    给你一个 二进制数组 nums 。
//
//    如果一个 子数组 中 不存在 两个 相邻 元素的值 相同 的情况，我们称这样的子数组为 交替子数组 。
//
//    返回数组 nums 中交替子数组的数量。
//
//    示例 1：
//
//    输入： nums = [0,1,1,1]
//
//    输出： 5
//
//    解释：
//
//    以下子数组是交替子数组：[0] 、[1] 、[1] 、[1] 以及 [0,1] 。
//
//    示例 2：
//
//    输入： nums = [1,0,1,0]
//
//    输出： 10
//
//    解释：
//
//    数组的每个子数组都是交替子数组。可以统计在内的子数组共有 10 个。
//
//    提示：
//
//    1 <= nums.length <= 105
//    nums[i] 不是 0 就是 1 。

    // 先找出所有有连续的范围,只要不在这个范围里的就符合要求,就数量+1
    public long countAlternatingSubarrays(int[] nums) {
        List<int[]> repeat = new ArrayList<>();
        int length = nums.length;
        int current = nums[0];
        int left = 0;
        int right = 0;
        for (int i = 1; i < length; i++) {
            if (nums[i] == current) {
                right = i;
                if (right == length - 1) {
                    repeat.add(new int[]{left,right});
                }
                continue;
            }
            if (left != right) {
                repeat.add(new int[]{left,right});
            }
            left = i;
            right = i;
            current = nums[i];
        }

        long result = length;
        for (int i = 1; i <= length; i++) {
            for (int j = 0; j < length-i; j++) {
                result = result + containsRepeat(j, j+i, repeat);
            }
        }
        return result;
    }

    private int containsRepeat(int left, int right, List<int[]> repeat) {
        for (int[] range : repeat) {
            if ( ! ((range[0] >= left && range[0] >= right) || (range[1] <= left && range[1] <= right))) {
                return 0;
            }
        }
        return 1;
    }


    // 上面的超时了,想复杂了,逆向思维就是下面的答案
    public long countAlternatingSubarrays2(int[] nums) {
        long result = 0, current = 0;
        int pre = -1;
        for (int a : nums) {
            current = (pre != a) ? current + 1 : 1;
            pre = a;
            result = result + current;
        }
        return result;
    }
}
